# source/bst/modCalculatablePolynomial.py

# A Calculatable Polynomial for use in our calculator, based on a previous homework's AddablePolynomial
# Ben Terris
# 11/28/2007

from modAddablePolynomial import AddablePolynomial
from modPolynomial import Polynomial
from modCalculatable import Calculatable

class CalculatablePolynomial(AddablePolynomial, Calculatable):
        '''A Polynomial class for use with our calculator. This class extends
        and implements the Calculatable interface with the exception of invert.
        '''
        
        def __div__(dividend, self):
                '''
                Find the quotient and remainder resulting of the division of
                this object and the dividend.
                
                Test division with remainder
                >>> x = cPoly7 / cPoly6
                >>> for entry in x:
                ...     print entry             
                1.0x^2 - 9.0x - 27.0
                -123.0
                1.0x - 3.0
                
                Test self-division
                >>> x = cPoly6 / cPoly6
                >>> for entry in x:
                ...     print entry
                1.0
                0
                1.0x - 3.0
                
                Test division with no remainder
                >>> x = cPoly8 / cPoly9
                >>> for entry in x:
                ...     print entry
                1.0x^4 + 6.0x^3 + 0.0
                0
                3.0x^3 + 1.0x^2

                '''
                if not isinstance(dividend, CalculatablePolynomial):
                        return None
                
                # lists of exponents
                selfexp = self._getSortedExponents()
                dividendexp = dividend._getSortedExponents()
                
                quotient = CalculatablePolynomial({})
                
                # loop through all possible exponents from highest to lowest
                for exp in range(dividendexp[0], 0, -1):
                        
                        newCoeff = ( dividend.getCoefficientByExponent(exp) /
                                     self.getCoefficientByExponent(selfexp[0]))

                        # keep going as long as the dividend's exponent is
                        # larger than the divisor's.
                        if exp >= selfexp[0]:
                                newExp = exp - selfexp[0]
                        else:
                                # early exit - not divisible
                                if quotient.__str__() == "0.0": 
                                        return [dividend, 0, self]
                                else:   # no exponents left,
                                        # return quotient and remainder
                                        return [quotient, dividend.getCoefficientByExponent(0), self]

                        quotient.setCoefficientByExponent(newExp, newCoeff)

                        # adjust the dividend for the next iteration
                        dividend = dividend - (self *CalculatablePolynomial({newExp:newCoeff}))

                        # early exit - no remainder
                        if dividend.__str__() == "0.0":
                                return [quotient, 0, self]
                        
                # division completed without any early exit conditions met
                # return quotient with any remainder
                return [quotient, dividend.getCoefficientByExponent(0), self]
                        
        def __mul__(self, rhs):
                '''Return the result of multiplying this object by rhs
                
        >>> print cPoly1; print cPoly2; print cPoly3
        8.0x^3 + 5.0x^2
        4.0x^6
        4.5x^16 + 7.2x^11 + 3.9x^8 + 2.0x^6 + 48.3x^3
        >>> print cPoly1 * cPoly2
        32.0x^9 + 20.0x^8
        >>> print cPoly1 * cPoly1 
        64.0x^6 + 80.0x^5 + 25.0x^4
        >>> print cPoly1 * cPoly3
        36.0x^19 + 22.5x^18 + 57.6x^14 + 36.0x^13 + 31.2x^11 + 19.5x^10 + 16.0x^9 + 10.0x^8 + 386.4x^6 + 241.5x^5
                '''
                polyDict, newPolyDict = {}, {}
                if not isinstance(rhs, CalculatablePolynomial):
                        return None
                
                for exp in rhs._getSortedExponents():                
                        polyDict[exp] = rhs.getCoefficientByExponent(exp)


                for exp in self._getSortedExponents():
                        for exp2 in polyDict:
                                newExponent = exp + exp2
                                newCoefficient = (self.getCoefficientByExponent(exp)
                                                  * polyDict[exp2])
                                        
                                if newPolyDict.has_key(newExponent):
                                        newPolyDict[newExponent] += newCoefficient
                                else:
                                                newPolyDict[newExponent] = (
                                                        newCoefficient)                        
                return CalculatablePolynomial( newPolyDict )


        def __sub__(self, rhs):
                '''Return the result of subtracting rhs from this object.
                
                >>> print cPoly1 - cPoly1
                0.0
                >>> print cPoly2 - cPoly1
                4.0x^6 - 8.0x^3 - 5.0x^2
                >>> print cPoly5 - cPoly4
                2.0x^4 + 2.0x^2

                '''
                if isinstance(rhs, CalculatablePolynomial):

                        return self + (-rhs)
                else:
                        return None

        def square(self):
                '''Return the square of this object.
                
                >>> print cPoly4.square()
                1.0x^4
                '''
                return self * self

        def __invert__(self):
                '''Unsupported operation.'''
                return None


if __name__ == '__main__':
        # run a battery of unit tests to ensure correct functionality
        cPoly1 = CalculatablePolynomial({3:8.0, 2:5.0})
        cPoly2 = CalculatablePolynomial({6:4.0})
        cPoly3 = CalculatablePolynomial({16:4.5, 11:7.2, 8:3.9, 6:2.0, 3:48.3})
        cPoly4 = CalculatablePolynomial({2:1.0})
        cPoly5 = CalculatablePolynomial({2:3.0, 4:2.0})
        cPoly6 = CalculatablePolynomial({1:1.0, 0:-3.0})
        cPoly7 = CalculatablePolynomial({3:1.0, 2:-12.0, 1:0.0, 0:-42.0})
        cPoly8 = CalculatablePolynomial({7:3.0, 6:19.0, 5:6.0})
        cPoly9 = CalculatablePolynomial({2:1.0, 3:3.0})

        
        def unittests():
                '''
                Test division with a long quotient.
                >>> x = cPoly8 / cPoly6
                >>> for item in x: print item
                3.0x^6 + 28.0x^5 + 90.0x^4 + 270.0x^3 + 810.0x^2 + 2430.0x + 7290.0
                21870.0
                1.0x - 3.0
                '''
        
        from doctest import testmod
        testmod(verbose=True)


